package wikisearch.cluster;

import org.jgrapht.alg.*;
import org.jgrapht.graph.Subgraph;

import wikisearch.datastructures.*;
import wikisearch.graphalgorithms.*;
import java.util.*;

/*
 * This class first calculates the min cut edges. 
 * Optimization : Detects if it makes a forest. If it does, then choose source within that forest.
 */
public class MinCutCluster {

	private Graph g = null;
	private int numClusters = 0;
	private HashMap<Integer, Set<String>> clusters = new HashMap<Integer, Set<String>>(); //stores clusterID, vertices in cluster.
	private final String sinkName = "artificial";
	double alpha = 0.1;
	int gsize = 0;
	
	public MinCutCluster(Graph g) {
		
		this.g = g;
		this.gsize = g.vertexSet().size();
		cluster();
	}
	
	public HashMap<Integer, Set<String>> getClusters() {
		
		return clusters;
	}
	
	public Set<String> getCluster(int cid) {
		
		return clusters.get(new Integer(cid));
	}
	/*
	 * This attempts at finding some min-cut
	 */
	private double mincut(Graph g, HashSet<WEdge> mincut, HashSet<String> cluster1, HashSet<String> cluster2) {

		String s = g.getRandomVert();
		String t = sinkName;
		double alpha = getAlpha(g);
		buildArtificialSink(g, t, alpha);
		
		System.out.println("Source : " + s);
		EdmondsKarpMaximumFlow<String, WEdge> maxflow = new EdmondsKarpMaximumFlow<String, WEdge>(g);
		maxflow.calculateMaximumFlow(s, t);
		Map<WEdge, Double> flowVals = maxflow.getMaximumFlow();
		double mincutval = MinCut.mincut(mincut, maxflow, flowVals, g, cluster1, cluster2);
		removeArtificialSink(g, t);
		
		return mincutval;
	}
	
	private void buildArtificialSink(Graph g, String vname, double alpha) {
		
		Object [] verts = g.vertexSet().toArray();
		g.addVertex(vname);
		for (Object v : verts) {
			if (!v.toString().equals(vname))
				g.setEdgeWeight(vname, v.toString(), alpha);
//			g.setEdgeWeight(v, vname, alpha);
		}
	}
	
	private void removeArtificialSink(Graph g, String vname) {
		
		g.removeVertex(vname);
	}
	
	private double getAlpha(Graph g) {

		alpha = 0.15 * (g.vertexSet().size() + 2.0) / ((double)gsize )  * Math.log((double)numClusters + 2.0);

		return alpha;//1.3; // alpha is determined in a totally random fashion.
	}
	
	private void cluster() {

		cluster(g);
	}
	
	private void cluster(Graph g) {
		
		if (g.vertexSet().size() < 1) return;
		
		HashSet<String> cluster1 = null;
		HashSet<String> cluster2 = null;
		HashSet<WEdge> mincut = null;	
		{
			cluster1 = new HashSet<String>();
			cluster2 = new HashSet<String>();
			
			double cutval = mincut(g, mincut, cluster1, cluster2);
			
			System.out.println("cluster1 : " + cluster1);
			System.out.println("cluster2 : " + cluster2);
			if (cluster2.contains(sinkName) && cluster2.size() <= 2 || cluster1.size() < 1) {
				
				cluster2.remove(sinkName);
				if (cluster1.size() < 1) {
					clusters.put(new Integer(numClusters++), cluster2);
				} else clusters.put(new Integer(numClusters++), cluster1);
			}
			
			else {
				System.out.println("Looping around");
				cluster2.remove(sinkName);
				if (cluster1.size() == 1) {
					clusters.put(new Integer(numClusters++), cluster1);
				}
				if (cluster2.size() == 1) {
					clusters.put(new Integer(numClusters++), cluster2);
				}
				Subgraph<String, WEdge, Graph> s1 = new Subgraph<String, WEdge, Graph>(g, cluster1);
				Subgraph<String, WEdge, Graph> s2 = new Subgraph<String, WEdge, Graph>(g, cluster2);
				
				cluster(new Graph(s1));
				cluster(new Graph(s2));			
			}
			/*
			if (inter < intra) {
				cluster(new Graph(s1));
				cluster(new Graph(s2));
				break;
			} else {
				if (s1.vertexSet().size() > 0)
					clusters.put(new Integer(numClusters++), s1.vertexSet());
				if (s2.vertexSet().size() > 0)
					clusters.put(new Integer(numClusters++), s2.vertexSet());
			}
			*/
		}
		System.out.println("Clusters are " + clusters);
	}
	
	private double getIntraScore(HashSet<WEdge> mincut, double cutval, Graph g1, Graph g2) {

		return 0.0;
	}
	
	private double getInterScore(HashSet<WEdge> mincut, double cutval,
			Graph g1, Graph g2) {
		
		return 0.0;
	}
}
